package graph.model;

import graph.config.Config;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;


public class Graph {
	private Map<String, Vertex> vertexTable;

	public Graph() {
		vertexTable = new HashMap<String, Vertex>();
	}

	/**
	 * Finds or creates the Vertex with given name
	 * 
	 * @param vertexName
	 * @return found or created Vertex
	 */
	public Vertex findCreateVertex( String vertexName ) {
		Vertex vertex = vertexTable.get( vertexName );

		/* If the Vertex isn't in the Map, create and add it */
		if( vertex == null ) {
			if( Config.debug )
				System.out.println( "Vertex " + vertexName + " created" );
			vertex = new Vertex( vertexName );
			vertexTable.put( vertexName, vertex );
		}
		return vertex;
	}

	/**
	 * Adds an Edge between the begin Vertex and the end Vertex with the given
	 * weight
	 * 
	 * @param begin
	 * @param end
	 * @param weight
	 */
	public void addEdge( Vertex begin, Vertex end, int weight ) {
		if( Config.debug )
			System.out.println( "Created edge between " + begin.getName() + " and " + end.getName() + " with weight " + weight );
		begin.addEdge( new Edge( begin, end, weight ) );
		end.addPredecessor( begin );
	}


	/**
	 * Sets the shortest value to 0 for start Vertexes
	 */
	public void setFirst() {
		for( Map.Entry<String, Vertex> m : vertexTable.entrySet() ) {
			Vertex vertex = m.getValue();
			if( vertex.isFirst() ) {
				vertex.setShortest( 0 );
				if( Config.debug )
					System.out.println( "Set first for " + m.getKey() );
				return;
			}
		}
	}

	/**
	 * Gets the start Vertex
	 * 
	 * @return
	 */
	public Vertex getRoot() {
		for( Map.Entry<String, Vertex> m : vertexTable.entrySet() ) {
			Vertex vertex = m.getValue();
			if( vertex.isFirst() ) {
				return vertex;
			}
		}
		return null;
	}

	/**
	 * Returns the last Vertex in the graph
	 * @return
	 */
	public Vertex getLast() {
		for( Map.Entry<String, Vertex> m : vertexTable.entrySet() ) {
			Vertex vertex = m.getValue();
			if( vertex.isLast() ) {
				return vertex;
			}
		}
		return null;
	}
	
	/* Onderstaande functies komen uit Generic Graph, zijn niet allemaal meer nodig maar staan verder niemand in de weg */

	/**
	 * A function to go breadthFirst through the Graph
	 * 
	 * @param root
	 * @return number of Vertexes in Graph
	 */
	public int countBreadthFirst( Vertex root ) {
		Queue<Vertex> queue = new LinkedList<Vertex>();
		ArrayList<Vertex> traceList = new ArrayList<Vertex>();
		queue.offer( root );
		while( ! queue.isEmpty() ) {
			Vertex vertex = queue.poll();
			if( Config.debug )
				System.out.println( "Visited " + vertex.getName() );
			for( Edge edge : vertex.getEdges() ) {
				Vertex end = edge.getEnd();
				if( ! traceList.contains( end ) ) {
					traceList.add( end );
					queue.add( end );
				}
			}
		}
		return traceList.size() + 1;
	}

	/**
	 * A function to go depthFirst through the Graph
	 * 
	 * @param root
	 * @return number of Vertexes in Graph
	 */
	public int countDepthFirst( Vertex root ) {
		return countDepthFirst( root, new ArrayList<Vertex>() );
	}

	/**
	 * A function to go depthFirst through the Graph
	 * 
	 * @param vertex
	 * @param traceList
	 * @return
	 */
	private int countDepthFirst( Vertex vertex, ArrayList<Vertex> traceList ) {
		if( Config.debug )
			System.out.println( "Visited " + vertex.getName() );
		for( Edge edge : vertex.getEdges() ) {
			Vertex end = edge.getEnd();
			if( ! traceList.contains( end ) ) {
				traceList.add( end );
				countDepthFirst( end, traceList );
			}
		}
		return traceList.size() + 1;
	}

	/**
	 * Print number of Vertex depthFirst
	 */
	public void printDepthFirst( String vertexName ) {
		System.out.println( countDepthFirst( vertexTable.get( vertexName ) ) );
	}

	/**
	 * Print number of Vertex breadthFirst
	 */
	public void printBreadthFirst( String vertexName ) {
		System.out.println( countBreadthFirst( vertexTable.get( vertexName ) ) );
	}

	/**
	 * For a nice overview
	 */
	public void print() {
		for( Map.Entry<String, Vertex> v : vertexTable.entrySet() ) {
			System.out.println( "[ " + v.getKey() + " ]" );
			v.getValue().print();
			System.out.println( "" );
		}
	}
}
